{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count the Number of Ideal Arrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming #combinatorics #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划 #组合数学 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: idealArrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计理想数组的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个整数 <code>n</code> 和 <code>maxValue</code> ，用于描述一个 <strong>理想数组</strong> 。</p>\n",
    "\n",
    "<p>对于下标从 <strong>0</strong> 开始、长度为 <code>n</code> 的整数数组 <code>arr</code> ，如果满足以下条件，则认为该数组是一个 <strong>理想数组</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每个 <code>arr[i]</code> 都是从 <code>1</code> 到 <code>maxValue</code> 范围内的一个值，其中 <code>0 &lt;= i &lt; n</code> 。</li>\n",
    "\t<li>每个 <code>arr[i]</code> 都可以被 <code>arr[i - 1]</code> 整除，其中 <code>0 &lt; i &lt; n</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回长度为 <code>n</code> 的 <strong>不同</strong> 理想数组的数目。由于答案可能很大，返回对 <code>10<sup>9</sup> + 7</code> 取余的结果。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 2, maxValue = 5\n",
    "<strong>输出：</strong>10\n",
    "<strong>解释：</strong>存在以下理想数组：\n",
    "- 以 1 开头的数组（5 个）：[1,1]、[1,2]、[1,3]、[1,4]、[1,5]\n",
    "- 以 2 开头的数组（2 个）：[2,2]、[2,4]\n",
    "- 以 3 开头的数组（1 个）：[3,3]\n",
    "- 以 4 开头的数组（1 个）：[4,4]\n",
    "- 以 5 开头的数组（1 个）：[5,5]\n",
    "共计 5 + 2 + 1 + 1 + 1 = 10 个不同理想数组。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 5, maxValue = 3\n",
    "<strong>输出：</strong>11\n",
    "<strong>解释：</strong>存在以下理想数组：\n",
    "- 以 1 开头的数组（9 个）：\n",
    "   - 不含其他不同值（1 个）：[1,1,1,1,1] \n",
    "   - 含一个不同值 2（4 个）：[1,1,1,1,2], [1,1,1,2,2], [1,1,2,2,2], [1,2,2,2,2]\n",
    "   - 含一个不同值 3（4 个）：[1,1,1,1,3], [1,1,1,3,3], [1,1,3,3,3], [1,3,3,3,3]\n",
    "- 以 2 开头的数组（1 个）：[2,2,2,2,2]\n",
    "- 以 3 开头的数组（1 个）：[3,3,3,3,3]\n",
    "共计 9 + 1 + 1 = 11 个不同理想数组。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= maxValue &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-the-number-of-ideal-arrays](https://leetcode.cn/problems/count-the-number-of-ideal-arrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-the-number-of-ideal-arrays](https://leetcode.cn/problems/count-the-number-of-ideal-arrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n5', '5\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\n",
    "        def factor(n):\n",
    "            ans = []\n",
    "            for i in range(2, int(sqrt(n + 0.5)) + 1):\n",
    "                while n % i == 0:\n",
    "                    ans.append(i)\n",
    "                    n //= i\n",
    "            if n > 1:\n",
    "                ans.append(n)\n",
    "            return ans\n",
    "        ans = 0\n",
    "        mod = 10 ** 9 + 7\n",
    "        comb = cache(math.comb)\n",
    "        for i in range(1, maxValue + 1):\n",
    "            c = Counter(factor(i))\n",
    "            tmp = 1\n",
    "            for key in c:\n",
    "                tmp *= comb(n - 1 + c[key], c[key])\n",
    "                tmp %= mod\n",
    "            ans += tmp\n",
    "            ans %= mod\n",
    "            # print(f\"i:{i}, c:{c}, tmp:{tmp}\")\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import comb\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, m: int) -> int:\n",
    "        M = 10 ** 9 + 7\n",
    "        ans = 1\n",
    "        for i in range(2, m + 1):\n",
    "            now = 1\n",
    "            for j in range(2, int(i ** 0.5) + 1):\n",
    "                if i % j == 0:\n",
    "                    cnt = 0\n",
    "                    while i % j == 0:\n",
    "                        i //= j\n",
    "                        cnt += 1\n",
    "                    now = now * comb(n + cnt - 1, n - 1) % M\n",
    "            if i != 1:\n",
    "                now = now * n % M\n",
    "            ans = (ans + now) % M\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 **9 + 7\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, mx: int) -> int:\n",
    "        res = mx\n",
    "        w = [1] * (mx+1)\n",
    "        for l in range(1,min(14,n)):\n",
    "            neww = [0] * (mx+1)\n",
    "            temp = 0\n",
    "            for i in range(1,mx//2+1):\n",
    "                cnt = 0\n",
    "                muti = 2\n",
    "                while i * muti <= mx:\n",
    "                    cnt += 1;neww[i * muti] += w[i];neww[i * muti] %= MOD;muti += 1\n",
    "                temp += w[i] * cnt % MOD\n",
    "            res += temp * comb(n-1,l) % MOD\n",
    "            w = neww\n",
    "        return res % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 **9 + 7\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, mx: int) -> int:\n",
    "        res = mx\n",
    "        w = [1] * (mx+1)\n",
    "        for l in range(1,min(14,n)):\n",
    "            neww = [0] * (mx+1)\n",
    "            temp = 0\n",
    "            for i in range(1,mx//2+1):\n",
    "                cnt = 0\n",
    "                muti = 2\n",
    "                while i * muti <= mx:\n",
    "                    cnt += 1;neww[i * muti] += w[i];muti += 1\n",
    "                temp += w[i] * cnt % MOD\n",
    "            res += temp * comb(n-1,l) % MOD\n",
    "            w = neww\n",
    "        return res % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 **9 + 7\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, mx: int) -> int:\n",
    "        res = mx\n",
    "        w = [1] * (mx+1)\n",
    "        for l in range(1,min(14,n)):\n",
    "            neww = [0] * (mx+1)\n",
    "            temp = 0\n",
    "            for i in range(1,mx//2+1):\n",
    "                cnt = 0\n",
    "                muti = 2\n",
    "                while i * muti <= mx:\n",
    "                    cnt += 1;neww[i * muti] += w[i];muti += 1\n",
    "                temp += w[i] * cnt\n",
    "            res += temp * comb(n-1,l)\n",
    "            w = neww\n",
    "        return res % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD,MX=10**9+7,10**4+1\n",
    "\n",
    "ks=[[]for _ in range(MX)] #ks[x]代表x分解质因数后，不同质因数的个数列表\n",
    "for i in range(2,MX):\n",
    "    p,x=2,i\n",
    "    while p*p<=x:\n",
    "        if x % p==0:\n",
    "            k=1\n",
    "            x//=p\n",
    "            while x%p==0:\n",
    "                k+=1\n",
    "                x//=p\n",
    "            ks[i].append(k)\n",
    "        p+=1\n",
    "    if x>1:ks[i].append(1)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\n",
    "        #数组的值范围被限制在1..maxValue,数组的长度也固定了\n",
    "        #下一个数可以被前一个数字整除（除第一个）,很严格的递增条件\n",
    "        #返回数目，需要取余\n",
    "\n",
    "        #n为10^4,maxValue为10^4\n",
    "        #对于这道题目，如果去研究每个位置能放的数，就中计了\n",
    "        #观察如下样例：当maxValue为2时，可以构造1 1 1 1 2 2 2 2，找到特殊的地方，在于倍增的位置。\n",
    "\n",
    "        #应该要发现的是，理想数组本质在于突然倍增的地方，我们不应该去关注那些没有倍增的位置，而枚举倍增的地方，可以看成是最后一个数字的质因数分解，在转变成组合数学问题\n",
    "        ans=0\n",
    "        for x in range(1,maxValue+1):\n",
    "            mul=1\n",
    "            for k in ks[x]:\n",
    "                mul=mul*comb(n+k-1,k)%MOD\n",
    "            ans+=mul\n",
    "        return ans%MOD\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD, MX = 10 ** 9 + 7, 10 ** 4 + 1\n",
    "\n",
    "ks = [[] for _ in range(MX)]  # ks[x] 为 x 分解质因数后，每个质因数的个数列表\n",
    "for i in range(2, MX):\n",
    "    p, x = 2, i\n",
    "    while p * p <= x:\n",
    "        if x % p == 0:\n",
    "            k = 1\n",
    "            x //= p\n",
    "            while x % p == 0:\n",
    "                k += 1\n",
    "                x //= p\n",
    "            ks[i].append(k)\n",
    "        p += 1\n",
    "    if x > 1: ks[i].append(1)\n",
    "\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\n",
    "        ans = 0\n",
    "        for x in range(1, maxValue + 1):\n",
    "            mul = 1\n",
    "            for k in ks[x]:\n",
    "                mul = mul * comb(n + k - 1, k) % MOD\n",
    "            ans += mul\n",
    "        return ans % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD, MX = 10 ** 9 + 7, 10 ** 4 + 1\n",
    "\n",
    "ks = [[] for _ in range(MX)]\n",
    "for i in range(2, MX):\n",
    "    p, x = 2, i\n",
    "    while p * p <= x:\n",
    "        if x % p == 0:\n",
    "            k = 1\n",
    "            x //= p\n",
    "            while x % p == 0:\n",
    "                k += 1\n",
    "                x //= p\n",
    "            ks[i].append(k)\n",
    "        p += 1\n",
    "    if x > 1:\n",
    "        ks[i].append(1)\n",
    "\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\n",
    "        ans = 0\n",
    "        for x in range(1, maxValue + 1):\n",
    "            mul = 1\n",
    "            for k in ks[x]:\n",
    "                mul = mul * comb(n + k - 1, k) % MOD\n",
    "            ans += mul\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD, MX = 10 ** 9 + 7, 10 ** 4 + 1\n",
    "\n",
    "ks = [[] for _ in range(MX)]  # ks[x] 为 x 分解质因数后，每个质因数的个数列表\n",
    "for i in range(2, MX):\n",
    "    p, x = 2, i\n",
    "    while p * p <= x:\n",
    "        if x % p == 0:\n",
    "            k = 1\n",
    "            x //= p\n",
    "            while x % p == 0:\n",
    "                k += 1\n",
    "                x //= p\n",
    "            ks[i].append(k)\n",
    "        p += 1\n",
    "    if x > 1: ks[i].append(1)\n",
    "\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\n",
    "        ans = 0\n",
    "        for x in range(1, maxValue + 1):\n",
    "            mul = 1\n",
    "            for k in ks[x]:\n",
    "                mul = mul * comb(n + k - 1, k) % MOD\n",
    "            ans += mul\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD, MX = 10 ** 9 + 7, 10 ** 4 + 1\n",
    "ks = [[] for _ in range(MX)]\n",
    "for i in range(2, MX):\n",
    "    p, x = 2, i\n",
    "    while p * p <= x:\n",
    "        if x % p == 0:\n",
    "            k = 1\n",
    "            x //=p\n",
    "            while x % p == 0:\n",
    "                k += 1\n",
    "                x //= p\n",
    "            ks[i].append(k)\n",
    "        p += 1\n",
    "    if x > 1: ks[i].append(1)\n",
    "\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\n",
    "        ans = 0\n",
    "        for x in range(1, maxValue + 1):\n",
    "            mul = 1\n",
    "            for k in ks[x]:\n",
    "                mul = mul * comb(n + k - 1, k) % MOD\n",
    "            ans += mul\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD, MX = 10 ** 9 + 7, 10 ** 4 + 1\n",
    "\n",
    "ks = [[] for _ in range(MX)]  # ks[x] 为 x 分解质因数后，每个质因数的个数列表\n",
    "for i in range(2, MX):\n",
    "    p, x = 2, i\n",
    "    while p * p <= x:\n",
    "        if x % p == 0:\n",
    "            k = 1\n",
    "            x //= p\n",
    "            while x % p == 0:\n",
    "                k += 1\n",
    "                x //= p\n",
    "            ks[i].append(k)\n",
    "        p += 1\n",
    "    if x > 1: ks[i].append(1)\n",
    "\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\n",
    "        ans = 0\n",
    "        for x in range(1, maxValue + 1):\n",
    "            mul = 1\n",
    "            for k in ks[x]:\n",
    "                mul = mul * comb(n + k - 1, k) % MOD\n",
    "            ans += mul\n",
    "        return ans % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD, MX = 10 ** 9 + 7, 10 ** 4 + 1\n",
    "primeFreq = [[] for _ in range(MX)] \n",
    "for j in range(2, MX):\n",
    "    n = j\n",
    "    res = []\n",
    "    for i in range(2, int(n ** 0.5) + 1):\n",
    "        while n % i == 0:\n",
    "            res.append(i)\n",
    "            n //= i\n",
    "    if n >= 2:\n",
    "        res.append(n)\n",
    "    primeFreq[j].extend(Counter(res).values())\n",
    "\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(1, maxValue + 1):\n",
    "            mul = 1\n",
    "            for k in primeFreq[i]:\n",
    "                mul = mul * comb(n + k - 1, k) % MOD\n",
    "            res += mul\n",
    "        return res % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD, MX = 10 ** 9 + 7, 10 ** 4 + 1\n",
    "ks = [[] for _ in range(MX)]  # ks[x] 为 x 分解质因数后，每个质因数的个数列表\n",
    "for j in range(2, MX):\n",
    "    n = j\n",
    "    res = []\n",
    "    for i in range(2, int(n ** 0.5) + 1):\n",
    "        while n % i == 0:\n",
    "            res.append(i)\n",
    "            n //= i\n",
    "    if n >= 2:\n",
    "        res.append(n)\n",
    "    ks[j].extend(Counter(res).values())\n",
    "\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\n",
    "        ans = 0\n",
    "        for x in range(1, maxValue + 1):\n",
    "            mul = 1\n",
    "            for k in ks[x]:\n",
    "                mul = mul * comb(n + k - 1, k) % MOD\n",
    "            ans += mul\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\n",
    "        M = 10**9+7\n",
    "        primes = [2]\n",
    "        for nn in range(3, maxValue+1):\n",
    "            for p in primes:\n",
    "                if nn % p == 0: break\n",
    "            else:\n",
    "                primes.append(nn)\n",
    "        divides = [[] for _ in range(maxValue+1)]\n",
    "        for x in range(2, maxValue+1):\n",
    "            divide = divides[x]\n",
    "            nn = x\n",
    "            for p in primes:\n",
    "                ex = 0\n",
    "                while nn > 1:\n",
    "                    nnn, r = divmod(nn, p)\n",
    "                    if r: break\n",
    "                    nn = nnn\n",
    "                    ex += 1\n",
    "                if ex:\n",
    "                    divide.append(ex)\n",
    "                    if nn == 1: break\n",
    "        res = 0\n",
    "        for x in range(1, maxValue + 1):\n",
    "            mul = 1\n",
    "            for k in divides[x]:\n",
    "                mul = mul * comb(n-1+k, k) % M\n",
    "            res += mul\n",
    "        return res % M\n",
    "        # \n",
    "        # R[n][m] = R[n-1][m//p]\n",
    "        # R[1][x] = 1\n",
    "        # 1 1\n",
    "        # 2 \n",
    "        # 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD, MX = 10 ** 9 + 7, 10 ** 4 + 1\n",
    "\n",
    "ks = [[] for _ in range(MX)]  # ks[x] 为 x 分解质因数后，每个质因数的个数列表\n",
    "for i in range(2, MX):\n",
    "    p, x = 2, i\n",
    "    while p * p <= x:\n",
    "        if x % p == 0:\n",
    "            k = 1\n",
    "            x //= p\n",
    "            while x % p == 0:\n",
    "                k += 1\n",
    "                x //= p\n",
    "            ks[i].append(k)\n",
    "        p += 1\n",
    "    if x > 1: ks[i].append(1)\n",
    "\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\n",
    "        ans = 0\n",
    "        for x in range(1, maxValue + 1):\n",
    "            mul = 1\n",
    "            for k in ks[x]:\n",
    "                mul = mul * comb(n + k - 1, k) % MOD\n",
    "            ans += mul\n",
    "        return ans % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD, MX = 10 ** 9 + 7, 10 ** 4 + 1\n",
    "\n",
    "ks = [[] for _ in range(MX)]  # ks[x] 为 x 分解质因数后，每个质因数的个数列表\n",
    "for i in range(2, MX):\n",
    "    p, x = 2, i\n",
    "    while p * p <= x:\n",
    "        if x % p == 0:\n",
    "            k = 1\n",
    "            x //= p\n",
    "            while x % p == 0:\n",
    "                k += 1\n",
    "                x //= p\n",
    "            ks[i].append(k)\n",
    "        p += 1\n",
    "    if x > 1: ks[i].append(1)\n",
    "\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\n",
    "        ans = 0\n",
    "        for x in range(1, maxValue + 1):\n",
    "            mul = 1\n",
    "            for k in ks[x]:\n",
    "                mul = mul * comb(n + k - 1, k) % MOD\n",
    "            ans += mul\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD, MX = 10 ** 9 + 7, 10 ** 4 + 1\n",
    "\n",
    "ks = [[] for _ in range(MX)]  # ks[x] 为 x 分解质因数后，每个质因数的个数列表\n",
    "for i in range(2, MX):\n",
    "    p, x = 2, i\n",
    "    while p * p <= x:\n",
    "        if x % p == 0:\n",
    "            k = 1\n",
    "            x //= p\n",
    "            while x % p == 0:\n",
    "                k += 1\n",
    "                x //= p\n",
    "            ks[i].append(k)\n",
    "        p += 1\n",
    "    if x > 1: ks[i].append(1)\n",
    "\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\n",
    "        ans = 0\n",
    "        for x in range(1, maxValue + 1):\n",
    "            mul = 1\n",
    "            for k in ks[x]:\n",
    "                mul = mul * comb(n + k - 1, k) % MOD\n",
    "            ans += mul\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD, MX = 10 ** 9 + 7, 10 ** 4 + 1\n",
    "\n",
    "ks = [[] for _ in range(MX)]  # ks[x] 为 x 分解质因数后，每个质因数的个数列表\n",
    "for i in range(2, MX):\n",
    "    p, x = 2, i\n",
    "    while p * p <= x:\n",
    "        if x % p == 0:\n",
    "            k = 1\n",
    "            x //= p\n",
    "            while x % p == 0:\n",
    "                k += 1\n",
    "                x //= p\n",
    "            ks[i].append(k)\n",
    "        p += 1\n",
    "    if x > 1: ks[i].append(1)\n",
    "\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\n",
    "        ans = 0\n",
    "        for x in range(1, maxValue + 1):\n",
    "            mul = 1\n",
    "            for k in ks[x]:\n",
    "                mul = mul * comb(n + k - 1, k) % MOD\n",
    "            ans += mul\n",
    "        return ans % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD, MX = 10 ** 9 + 7, 10 ** 4 + 1\n",
    "\n",
    "ks = [[] for _ in range(MX)]  # ks[x] 为 x 分解质因数后，每个质因数的个数列表\n",
    "for i in range(2, MX):\n",
    "    p, x = 2, i\n",
    "    while p * p <= x:\n",
    "        if x % p == 0:\n",
    "            k = 1\n",
    "            x //= p\n",
    "            while x % p == 0:\n",
    "                k += 1\n",
    "                x //= p\n",
    "            ks[i].append(k)\n",
    "        p += 1\n",
    "    if x > 1: ks[i].append(1)\n",
    "\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\n",
    "        ans = 0\n",
    "        for x in range(1, maxValue + 1):\n",
    "            mul = 1\n",
    "            for k in ks[x]:\n",
    "                mul = mul * comb(n + k - 1, k) % MOD\n",
    "            ans += mul\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD, MX =10**9 + 7, 10**4 + 1\n",
    "ks = [[] for _ in range(MX)]\n",
    "for i in range(2, MX):\n",
    "    p, x = 2, i\n",
    "    while p * p <= x:\n",
    "        if x % p == 0:\n",
    "            k = 1\n",
    "            x //= p\n",
    "            while x % p == 0:\n",
    "                k += 1\n",
    "                x //= p\n",
    "            ks[i].append(k)\n",
    "        p += 1\n",
    "    if x > 1:\n",
    "        ks[i].append(1)\n",
    "    \n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\n",
    "        ans = 0\n",
    "        for x in range(1, maxValue + 1):\n",
    "            mul = 1\n",
    "            for k in ks[x]:\n",
    "                mul = mul * comb(n + k - 1, k) % MOD\n",
    "            ans += mul\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD, MX = 10 ** 9 + 7, 10 ** 4 + 1\n",
    "\n",
    "ks = [[] for _ in range(MX)]  # ks[x] 为 x 分解质因数后，每个质因数的个数列表\n",
    "for i in range(2, MX):\n",
    "    p, x = 2, i\n",
    "    while p * p <= x:\n",
    "        if x % p == 0:\n",
    "            k = 1\n",
    "            x //= p\n",
    "            while x % p == 0:\n",
    "                k += 1\n",
    "                x //= p\n",
    "            ks[i].append(k)\n",
    "        p += 1\n",
    "    if x > 1: ks[i].append(1)\n",
    "\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\n",
    "        ans = 0\n",
    "        for x in range(1, maxValue + 1):\n",
    "            mul = 1\n",
    "            for k in ks[x]:\n",
    "                mul = mul * comb(n + k - 1, k) % MOD\n",
    "            ans += mul\n",
    "        return ans % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD, MX = 10 ** 9 + 7, 10 ** 4 + 1\n",
    "\n",
    "ks = [[] for _ in range(MX)]\n",
    "\n",
    "for i in range(2,MX):\n",
    "    p, x = 2, i\n",
    "    while p * p <= x:\n",
    "        if x % p == 0:\n",
    "            k = 1\n",
    "            x //= p\n",
    "            while x % p == 0:\n",
    "                k += 1\n",
    "                x //= p\n",
    "            ks[i].append(k)\n",
    "        p += 1\n",
    "    if x > 1: ks[i].append(1)\n",
    "\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\n",
    "        ans = 0\n",
    "        for x in range(1, maxValue + 1):\n",
    "            mul = 1\n",
    "            for k in ks[x]:\n",
    "                mul = mul * comb(n + k - 1, k) % MOD\n",
    "            ans += mul\n",
    "        return ans % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD, MX = 10 ** 9 + 7, 10 ** 4 + 1\n",
    "\n",
    "ks = [[] for _ in range(MX)]  # ks[x] 为 x 分解质因数后，每个质因数的个数列表\n",
    "for i in range(2, MX):\n",
    "    p, x = 2, i\n",
    "    while p * p <= x:\n",
    "        if x % p == 0:\n",
    "            k = 1\n",
    "            x //= p\n",
    "            while x % p == 0:\n",
    "                k += 1\n",
    "                x //= p\n",
    "            ks[i].append(k)\n",
    "        p += 1\n",
    "    if x > 1: ks[i].append(1)\n",
    "\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\n",
    "        ans = 0\n",
    "        for x in range(1, maxValue + 1):\n",
    "            mul = 1\n",
    "            for k in ks[x]:\n",
    "                mul = mul * comb(n + k - 1, k) % MOD\n",
    "            ans += mul\n",
    "        return ans % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD, MX = 10 ** 9 + 7, 10 ** 4 + 1\n",
    "\n",
    "ks = [[] for _ in range(MX)]  # ks[x] 为 x 分解质因数后，每个质因数的个数列表\n",
    "for i in range(2, MX):\n",
    "    p, x = 2, i\n",
    "    while p * p <= x:\n",
    "        if x % p == 0:\n",
    "            k = 1\n",
    "            x //= p\n",
    "            while x % p == 0:\n",
    "                k += 1\n",
    "                x //= p\n",
    "            ks[i].append(k)\n",
    "        p += 1\n",
    "    if x > 1: ks[i].append(1)\n",
    "\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\n",
    "        ans = 0\n",
    "        for x in range(1, maxValue + 1):\n",
    "            mul = 1\n",
    "            for k in ks[x]:\n",
    "                mul = mul * comb(n + k - 1, k) % MOD\n",
    "            ans += mul\n",
    "        return ans % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "@cache\n",
    "def dpf_count(x):\n",
    "    p = 2\n",
    "    ret = []\n",
    "    while p * p <= x:\n",
    "        if x % p == 0:\n",
    "            k = 1\n",
    "            x //= p\n",
    "            while x % p == 0:\n",
    "                k += 1\n",
    "                x //= p\n",
    "\n",
    "            ret.append(k)\n",
    "\n",
    "        p += 1\n",
    "\n",
    "    if x > 1:\n",
    "        ret.append(1)\n",
    "\n",
    "    return ret\n",
    "\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\n",
    "        ret = 0\n",
    "\n",
    "        for x in range(1, maxValue + 1):\n",
    "            y = 1\n",
    "\n",
    "            for k in dpf_count(x):\n",
    "                y *= (comb(n + k - 1, k) % MOD)\n",
    "                y %= MOD\n",
    "\n",
    "            ret += y\n",
    "            ret %= MOD\n",
    "\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ball:\n",
    "    \"\"\"https://qiita.com/drken/items/f2ea4b58b0d21621bd51\"\"\"\n",
    "\n",
    "    __slots__ = (\"_fac\", \"_ifac\", \"_inv\", \"_mod\")\n",
    "\n",
    "    def __init__(self, size: int, mod: int) -> None:\n",
    "        self._mod = mod\n",
    "        self._fac = [1]\n",
    "        self._ifac = [1]\n",
    "        self._inv = [1]\n",
    "        self._expand(size)\n",
    "\n",
    "    def query(\n",
    "        self,\n",
    "        n: int,\n",
    "        k: int,\n",
    "        *,\n",
    "        isBallSame: bool,\n",
    "        isBoxSame: bool,\n",
    "        atMostOneBallPerBox=False,\n",
    "        noLimitWithBox=False,\n",
    "        atLeastOneBallPerBox=False,\n",
    "    ) -> int:\n",
    "        \"\"\"n个球放入k个盒子的方案数.\n",
    "\n",
    "        Args:\n",
    "            isBallSame (bool): 球是否有区别.\n",
    "            isBoxSame (bool): 盒子是否有区别.\n",
    "            atMostOneBalPerBox (bool, optional): 每个盒子最多放一个球.\n",
    "            noLimitWithBox (bool, optional): 每个盒子可以放任意个球.\n",
    "            atLeastOneBallPerBox (bool, optional): 每个盒子至少放一个球.\n",
    "        \"\"\"\n",
    "        limits = (atMostOneBallPerBox, noLimitWithBox, atLeastOneBallPerBox)\n",
    "        assert limits.count(True) == 1, \"Must have one limit and only one limit with box.\"\n",
    "        if isBallSame and isBoxSame:\n",
    "            if atMostOneBallPerBox:\n",
    "                return self._solve1(n, k)\n",
    "            if noLimitWithBox:\n",
    "                return self._solve2(n, k)\n",
    "            if atLeastOneBallPerBox:\n",
    "                return self._solve3(n, k)\n",
    "        if not isBallSame and isBoxSame:\n",
    "            if atMostOneBallPerBox:\n",
    "                return self._solve4(n, k)\n",
    "            if noLimitWithBox:\n",
    "                return self._solve5(n, k)\n",
    "            if atLeastOneBallPerBox:\n",
    "                return self._solve6(n, k)\n",
    "        if isBallSame and not isBoxSame:\n",
    "            if atMostOneBallPerBox:\n",
    "                return self._solve7(n, k)\n",
    "            if noLimitWithBox:\n",
    "                return self._solve8(n, k)\n",
    "            if atLeastOneBallPerBox:\n",
    "                return self._solve9(n, k)\n",
    "        if not isBallSame and not isBoxSame:\n",
    "            if atMostOneBallPerBox:\n",
    "                return self._solve10(n, k)\n",
    "            if noLimitWithBox:\n",
    "                return self._solve11(n, k)\n",
    "            if atLeastOneBallPerBox:\n",
    "                return self._solve12(n, k)\n",
    "\n",
    "        raise Exception(\"Unreachable code.\")\n",
    "\n",
    "    def _solve1(self, n: int, k: int) -> int:\n",
    "        \"\"\"n个不同的球，放入k个不同的盒子(每个盒子最多放一个球).\"\"\"\n",
    "        return self.P(n, k)\n",
    "\n",
    "    def _solve2(self, n: int, k: int) -> int:\n",
    "        \"\"\"n个不同的球，放入k个不同的盒子(每个盒子可以放任意个球).\"\"\"\n",
    "        return pow(k, n, self._mod)\n",
    "\n",
    "    def _solve3(self, n: int, k: int) -> int:\n",
    "        \"\"\"n个不同的球，放入k个不同的盒子(每个盒子至少放一个球).\n",
    "        容斥原理:用总方案数减去不合法的方案数.\n",
    "        O(k*logn)\n",
    "        \"\"\"\n",
    "        mod = self._mod\n",
    "        res = 0\n",
    "        for i in range(k + 1):\n",
    "            if (k - i) & 1:\n",
    "                res -= self.C(k, i) * pow(i, n, mod)\n",
    "            else:\n",
    "                res += self.C(k, i) * pow(i, n, mod)\n",
    "            res %= mod\n",
    "        return res\n",
    "\n",
    "    def _solve4(self, n: int, k: int) -> int:\n",
    "        \"\"\"n个相同的球，放入k个不同的盒子(每个盒子最多放一个球).\"\"\"\n",
    "        return self.C(n, k)\n",
    "\n",
    "    def _solve5(self, n: int, k: int) -> int:\n",
    "        \"\"\"n个相同的球，放入k个不同的盒子(每个盒子可以放任意个球).\"\"\"\n",
    "        return self.C(n + k - 1, n)\n",
    "\n",
    "    def _solve6(self, n: int, k: int) -> int:\n",
    "        \"\"\"n个相同的球，放入k个不同的盒子(每个盒子至少放一个球).\"\"\"\n",
    "        return self.C(n - 1, k - 1)\n",
    "\n",
    "    def _solve7(self, n: int, k: int) -> int:\n",
    "        \"\"\"n个不同的球，放入k个相同的盒子(每个盒子最多放一个球).\"\"\"\n",
    "        return 0 if n > k else 1\n",
    "\n",
    "    def _solve8(self, n: int, k: int) -> int:\n",
    "        \"\"\"n个不同的球，放入k个相同的盒子(每个盒子可以放任意个球).\n",
    "        贝尔数B(n,k).\n",
    "        O(min(n,k)*logn).\n",
    "        \"\"\"\n",
    "        return self.bell(n, k)\n",
    "\n",
    "    def _solve9(self, n: int, k: int) -> int:\n",
    "        \"\"\"n个不同的球，放入k个相同的盒子(每个盒子至少放一个球).\n",
    "        第二类斯特林数S(n,k).\n",
    "        O(k*logn).\n",
    "        \"\"\"\n",
    "        return self.stirling2(n, k)\n",
    "\n",
    "    def _solve10(self, n: int, k: int) -> int:\n",
    "    \n",
    "        \"\"\"n个相同的球，放入k个相同的盒子(每个盒子最多放一个球).\"\"\"\n",
    "        return 0 if n > k else 1\n",
    "\n",
    "    def _solve11(self, n: int, k: int) -> int:\n",
    "        \"\"\"n个相同的球，放入k个相同的盒子(每个盒子可以放任意个球).\n",
    "        分割数P(n,k).\n",
    "        \"\"\"\n",
    "        return self.partition(n, k)\n",
    "\n",
    "    def _solve12(self, n: int, k: int) -> int:\n",
    "        \"\"\"n个相同的球，放入k个相同的盒子(每个盒子至少放一个球).\n",
    "        分割数P(n-k,k).\n",
    "        \"\"\"\n",
    "        if n < k:\n",
    "            return 0\n",
    "        return self.partition(n - k, k)\n",
    "\n",
    "    def fac(self, k: int) -> int:\n",
    "        self._expand(k)\n",
    "        return self._fac[k]\n",
    "\n",
    "    def ifac(self, k: int) -> int:\n",
    "        self._expand(k)\n",
    "        return self._ifac[k]\n",
    "\n",
    "    def inv(self, k: int) -> int:\n",
    "        self._expand(k)\n",
    "        return self._inv[k]\n",
    "\n",
    "    def C(self, n: int, k: int) -> int:\n",
    "        if n < 0 or k < 0 or n < k:\n",
    "            return 0\n",
    "        mod = self._mod\n",
    "        return self.fac(n) * self.ifac(k) % mod * self.ifac(n - k) % mod\n",
    "\n",
    "    def P(self, n: int, k: int) -> int:\n",
    "        if n < 0 or k < 0 or n < k:\n",
    "            return 0\n",
    "        mod = self._mod\n",
    "        return self.fac(n) * self.ifac(n - k) % mod\n",
    "\n",
    "    def H(self, n: int, k: int) -> int:\n",
    "        \"\"\"可重复选取元素的组合数\"\"\"\n",
    "        if n == 0:\n",
    "            return 1 if k == 0 else 0\n",
    "        return self.C(n + k - 1, k)\n",
    "\n",
    "    def put(self, n: int, k: int) -> int:\n",
    "        \"\"\"n个相同的球放入k个不同的盒子(盒子可放任意个球)的方案数.\"\"\"\n",
    "        return self.C(n + k - 1, n)\n",
    "\n",
    "    def partition(self, n: int, k: int) -> int:\n",
    "        \"\"\"O(n*k)\"\"\"\n",
    "        dp = [[0] * (k + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(n + 1):\n",
    "            for j in range(1, k + 1):\n",
    "                if i >= j:\n",
    "                    dp[i][j] = dp[i][j - 1] + dp[i - j][j]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i][j - 1]\n",
    "        return dp[n][k]\n",
    "\n",
    "    def bell(self, n: int, k: int) -> int:\n",
    "        \"\"\"O(min(n,k)*logn)\"\"\"\n",
    "        if k > n:\n",
    "            k = n\n",
    "        mod = self._mod\n",
    "        jsum = [0] * (k + 2)\n",
    "        for j in range(k + 1):\n",
    "            add = self.ifac(j)\n",
    "            if j & 1:\n",
    "                jsum[j + 1] = (jsum[j] - add) % mod\n",
    "            else:\n",
    "                jsum[j + 1] = (jsum[j] + add) % mod\n",
    "        res = 0\n",
    "        for i in range(k + 1):\n",
    "            res += pow(i, n, mod) * self.ifac(i) % MOD * jsum[k - i + 1]\n",
    "            res %= mod\n",
    "        return res\n",
    "\n",
    "    def stirling2(self, n: int, k: int) -> int:\n",
    "        \"\"\"O(k*logn)\"\"\"\n",
    "        mod = self._mod\n",
    "        res = 0\n",
    "        for i in range(k + 1):\n",
    "            if (k - i) & 1:\n",
    "                res -= self.C(k, i) * pow(i, n, mod)\n",
    "            else:\n",
    "                res += self.C(k, i) * pow(i, n, mod)\n",
    "            res %= mod\n",
    "        return res * self.ifac(k) % mod\n",
    "\n",
    "    def _expand(self, size: int) -> None:\n",
    "        if len(self._fac) < size + 1:\n",
    "            mod = self._mod\n",
    "            preSize = len(self._fac)\n",
    "            diff = size + 1 - preSize\n",
    "            self._fac += [1] * diff\n",
    "            self._ifac += [1] * diff\n",
    "            self._inv += [1] * diff\n",
    "            for i in range(preSize, size + 1):\n",
    "                self._fac[i] = self._fac[i - 1] * i % mod\n",
    "            self._ifac[size] = pow(self._fac[size], mod - 2, mod)  # !modInv\n",
    "            for i in range(size - 1, preSize - 1, -1):\n",
    "                self._ifac[i] = self._ifac[i + 1] * (i + 1) % mod\n",
    "            for i in range(preSize, size + 1):\n",
    "                self._inv[i] = self._ifac[i] * self._fac[i - 1] % mod\n",
    "\n",
    "class PrimeTable:\n",
    "    def __init__(self, n=int((10**9)**0.5)+3) -> None:\n",
    "        #值域1e9的话考虑质因子，只需小于等于(10**9)**0.5的质数即可\n",
    "        #任意一个正整数n最多只有一个质因子大于根号n\n",
    "        self.n = n\n",
    "        self.primes = [] #小于等于n的所有质数\n",
    "        self.min_div = [0] * (n+1)\n",
    "        self.min_div[1] = 1\n",
    " \n",
    "        mu = [0] * (n+1)\n",
    "        phi = [0] * (n+1)\n",
    "        mu[1] = 1\n",
    "        phi[1] = 1\n",
    " \n",
    "        for i in range(2, n+1):\n",
    "            if not self.min_div[i]:\n",
    "                self.primes.append(i)\n",
    "                self.min_div[i] = i\n",
    "                mu[i] = -1\n",
    "                phi[i] = i-1\n",
    "            for p in self.primes:\n",
    "                if i * p > n: break\n",
    "                self.min_div[i*p] = p\n",
    "                if i % p == 0:\n",
    "                    phi[i*p] = phi[i] * p\n",
    "                    break\n",
    "                else:\n",
    "                    mu[i*p] = -mu[i]\n",
    "                    phi[i*p] = phi[i] * (p - 1)\n",
    "    # x是否质数\n",
    "    def is_prime(self, x:int):\n",
    "        if x < 2: return False\n",
    "        if x <= self.n: return self.min_div[x] == x\n",
    "        for p in self.primes:\n",
    "            if p * p > x: break\n",
    "            if x % i == 0: return False\n",
    "        return True\n",
    "\n",
    "    # x分解质因数:[p, cnt] 质因子p，个数cnt\n",
    "    # 用的yield，当作一个可遍历的数据对象\n",
    "    #一个数一定可以分解为多个质数的连乘积\n",
    "    #n = x^a * y^b * z^c ...  （x,y,z为质因数） n的约数个数=(a+1)(b+1)...(y+1)\n",
    "\n",
    "    def prime_factorization(self, x:int):\n",
    "        for p in self.primes:\n",
    "            if p * p > x: break\n",
    "            if x <= self.n: break\n",
    "            if x % p == 0:\n",
    "                cnt = 0\n",
    "                while x % p == 0: cnt += 1; x //= p\n",
    "                yield p, cnt\n",
    "        while (1 < x and x <= self.n):\n",
    "            p, cnt = self.min_div[x], 0\n",
    "            while x % p == 0: cnt += 1; x //= p\n",
    "            yield p, cnt\n",
    "        if x >= self.n and x > 1:\n",
    "            #小于等于(10**9)**0.5的质数除干净了，如果还大于1\n",
    "            # 那么余下的数一定是一个大于等于n的质数\n",
    "            yield x, 1\n",
    "            \n",
    "    # x的所有因数\n",
    "    def get_factors(self, x:int):\n",
    "        factors = [1]\n",
    "        for p, b in self.prime_factorization(x):\n",
    "            n = len(factors)\n",
    "            for j in range(1, b+1):\n",
    "                for d in factors[:n]:\n",
    "                    factors.append(d * (p ** j))\n",
    "\n",
    "mod=10**9+7\n",
    "\n",
    "b=ball(10**4+5,mod)\n",
    "\n",
    "pt=PrimeTable(10**4+5)\n",
    "\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\n",
    "        res=0\n",
    "        for i in range(1,maxValue+1):\n",
    "            ans=1\n",
    "            for p,c in pt.prime_factorization(i):\n",
    "                ans=(ans*b._solve5(c,n))%mod\n",
    "            res=(res+ans)%mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    facts = [[] for _ in range(10001)]\n",
    "    def idealArrays(self, n: int, m: int) -> int:\n",
    "        def facts_init() -> None:\n",
    "            for i in range(m, 1, -1):\n",
    "                if self.facts[i]: return\n",
    "                for k in range(1, int(i ** 0.5) + 1):\n",
    "                    if i % k == 0: self.facts[i].append(k)\n",
    "                for j in range(len(self.facts[i]) - 1, 0, -1):\n",
    "                    k = self.facts[i][j]\n",
    "                    if k * k != i: self.facts[i].append(i // k)\n",
    "        def mod_pow(a: int, p: int) -> int:\n",
    "            if p == 0: return 1\n",
    "            b = mod_pow(a, p >> 1)\n",
    "            if p & 1 == 0: return b * b % MOD\n",
    "            if p & 1 == 1: return b * b % MOD * a % MOD\n",
    "        def mod_div(a: int, b: int) -> int:\n",
    "            return a * mod_pow(b, MOD - 2) % MOD\n",
    "        def C(n: int, k: int) -> int:\n",
    "            return mod_div(F[n], F[n - k] * F[k] % MOD)\n",
    "        def solve(curr: int, k: int) -> None:\n",
    "            nums[k] += 1\n",
    "            for next in self.facts[curr]: solve(next, k + 1)\n",
    "        ans = 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        F = [1] * n\n",
    "        nums = [0] * 15\n",
    "        if not self.facts[m]: facts_init()\n",
    "        for i in range(1, n): F[i] = F[i - 1] * i % MOD\n",
    "        for i in range(1, m + 1): solve(i, 1)\n",
    "        for i, k in enumerate(nums[:n+1]):\n",
    "            if k != 0: ans = (ans + k * C(n - 1, i - 1)) % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# consider the ideal array with i distinct integers, ending at j:\r\n",
    "# dp[i][j] := number of i length ideal array with distinct integers, ending at j\r\n",
    "# dp[0][1] = 1\r\n",
    "# dp[i][j] = sum(dp[i - 1][k]), j % k == 0\r\n",
    "# longest such array is 1, 2, 4, .., 2**(i - 1) <= maxValue <= 1e4 < 2^14\r\n",
    "# i < 15\r\n",
    "# with any of such array, an ideal array of length n can be constructed by duplicating elements\r\n",
    "# in nCr(n - 1, i - 1) ways\r\n",
    "from functools import cache\r\n",
    "from math import floor, log2, comb\r\n",
    "mod = 1000000007\r\n",
    "dp: list[dict[int, int]] = [dict() for _ in range(15)]\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\r\n",
    "        res = 0\r\n",
    "        m = 1 + min(n, floor(log2(maxValue)) + 1)\r\n",
    "        for i in range(m): dp[i].clear()\r\n",
    "        for i in range(maxValue):\r\n",
    "            dp[1][i + 1] = 1\r\n",
    "\r\n",
    "        for i in range(1, m):\r\n",
    "            for j, cnt in dp[i].items():\r\n",
    "                res += cnt * cache(comb)(n - 1, i - 1)\r\n",
    "                res %= mod\r\n",
    "                k = j + j\r\n",
    "                while k <= maxValue:\r\n",
    "                    dp[i + 1].setdefault(k, 0)\r\n",
    "                    dp[i + 1][k] += cnt\r\n",
    "                    k += j\r\n",
    "        \r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def fact(n):\n",
    "    cnt = Counter()\n",
    "    while n > 1:\n",
    "        for p in range(2, n + 1):\n",
    "            if n % p == 0:\n",
    "                cnt[p] += 1\n",
    "                n //= p\n",
    "                break\n",
    "    return cnt\n",
    "\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\n",
    "        res = 0\n",
    "        for v in range(1, maxValue + 1):\n",
    "            f = fact(v)\n",
    "            res += reduce(operator.mul,[comb(n+k-1,k) for k in f.values()],1)\n",
    "        return res % (10**9+7)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@lru_cache(None)\n",
    "def breakdown(num):\n",
    "    i = 2\n",
    "    cnt = Counter()\n",
    "    while i * i <= num:\n",
    "        while num % i == 0:\n",
    "            num //= i\n",
    "            cnt[i] += 1\n",
    "        i += 1\n",
    "    if num > 1:\n",
    "        cnt[num] += 1\n",
    "    return cnt\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(1, maxValue + 1):\n",
    "            cnt = breakdown(i)\n",
    "            res = 1\n",
    "            for v in cnt.values():\n",
    "                res *= comb(n + v - 1, v)\n",
    "                res %= kmod\n",
    "\n",
    "            ans += res\n",
    "            ans %= kmod\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\n",
    "        \"\"\"\n",
    "        数论\n",
    "        分别考虑以x结尾长度为n的理想数组有多少个，数组结尾可以是1 ~ maxValue，因此把这些情况累加，就是最终结果。\n",
    "        以结尾为4、长度为5进行分析：\n",
    "        4的前面可以是4、2、1， 2的前面可以是2、1， 1的前面只能是1。例如：\n",
    "        [1, 2, 2, 4, 4]\n",
    "        [1, 1, 1, 4, 4]\n",
    "        [2, 2, 2, 4, 4]\n",
    "        [4, 4, 4, 4, 4]\n",
    "        以[1, 2, 2, 4, 4]为例，可以记为 [_, *2, _, *2, _]，只需记录在哪些位置的元素发生了改变(倍增)，\n",
    "        从当前倍增的位置开始 ~ 下一次倍增的位置之前(或数组结尾)，将会一直维持这个值。\n",
    "        可假设每个数组的开头前面有一个值1，若数组中的第一个元素为1，则没有发生倍增；若第一个元素不是1，则发生了倍增。\n",
    "        例如：[2, 2, 2, 4, 4] 可表示为 [*2, _, _, *2, _]；\n",
    "        在同一个位置可以发生多次倍增，例如：[1, 1, 1, 4, 4] 可表示为 [_, _, _, *2*2, _]；[4, 4, 4, 4, 4] 可表示为 [*2*2, _, _, _, _]。\n",
    "        由于固定了结尾为4，而4的质因子为2、2，即 4 = (1) * 2 * 2\n",
    "        所有结尾为4、长度为5的理想数组，问题可转化为 结尾数字(4)的质因子可以放在哪些位置，当前有5个不同的位置，2个质因子2，\n",
    "        从5个位置中选择一个(将2个2放在一个位置)或两个(将2个2放在不同位置)，因为2个2是相同的，谁先谁后，结果都是一样的。所以这是个组合问题。\n",
    "        问题进一步转化为：把k个相同的小球放进n个不同的盒子中，允许有些盒子为空，也允许一个盒子中放入多个小球，有多少种不同的放法？\n",
    "        该问题可用隔板法来求解，把n个盒子当做n-1个隔板，然后加上k个小球，相当于总共有 n-1 + k 个位置，从中选出n-1个位置放隔板，\n",
    "        即方案数为：C(n-1+k)(n-1)\n",
    "        由于maxValue <= 10^4，质因子最小为2，2^13 = 8192 < 10^4 < 16384 = 2^14，质因子越大，质因子的个数将会越小，\n",
    "        所以质因子为2时，质因子的个数k才能达到最大值13，即 k <= 13。所以上面的 C(n-1+k)(n-1) 可写为 C(n-1+k)(k) ，k 显然远小于n-1.\n",
    "        若结尾数字由多个不同的质因子组成，例如：k1个2、k2个3、k3个5，则可将问题分解为：\n",
    "        1、从n-1 + k1个位置中选出k1个位置放质因子2，得到 C(n-1+k1)(k1)\n",
    "        2、从n-1 + k2个位置中选出k2个位置放质因子3，得到 C(n-1+k2)(k2)\n",
    "        3、从n-1 + k3个位置中选出k3个位置放质因子5，得到 C(n-1+k3)(k3)\n",
    "        这3种情况之间互不影响：放质因子5的时候，不用关心这个位置之前放没放过2、3，以及放了多少个2、多少个3。\n",
    "        所以可采用乘法原理来计算最终结果：C(n-1+k1)(k1) * C(n-1+k2)(k2) * C(n-1+k3)(k3)\n",
    "\n",
    "        综上，原问题最终转化为：质因数分解出所有的质因子及其个数(其实只关注个数k) + 计算组合数问题\n",
    "        计算组合数问题 可用动态规划进行计算，假设dp[i][j] 表示从i个位置中选择j个，即 C(i)(j)。该问题可分为两种情况：\n",
    "        1、选择了位置i，则只需再从i-1个位置中选择j-1个，即 C(i-1)(j-1)\n",
    "        2、未选择位置i，则需要从i-1个位置中选择j个，即 C(i-1)(j)\n",
    "        所以，dp[i][j] = dp[i-1][j-1] + dp[i-1][j]\n",
    "        \"\"\"\n",
    "        mod = 10 ** 9 + 7\n",
    "        max_k = 13\n",
    "        # n-1+13 +1\n",
    "        max_n = n + max_k\n",
    "        dp = [[0] * (max_k + 1) for _ in range(max_n)]\n",
    "        # 初始值，从0个位置中选出0个，只有一种方案\n",
    "        dp[0][0] = 1\n",
    "        # 预处理出 1 ~ n-1+13 的所有组合数\n",
    "        for i in range(1, max_n):\n",
    "            # 从任意个位置中选出0个，都只有一种方案\n",
    "            dp[i][0] = 1\n",
    "            for j in range(1, min(i, max_k) + 1):\n",
    "                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % mod\n",
    "\n",
    "        # 预处理 2 ~ maxValue 的所有数x，将这些数分解出所有的质因子，然后记录各个质因子的个数k。\n",
    "        # 由于并不关心个数k具体对应哪个质因子，所以使用数组记录个数k即可，而无需使用字典记录 个数k ——> 质因子\n",
    "        ks = [[] for _ in range(maxValue + 1)]\n",
    "        for i in range(2, maxValue + 1):\n",
    "            # 质因子p从2开始：2、3、5、7、……\n",
    "            p, x = 2, i\n",
    "            # 不用担心会记录质因子4的个数，质因子4的个数一定为0，因为能被4整除，就一定能被2整除，x先被2整除过若干次后，直到不能被2整除，\n",
    "            # 质因子p才会加1变成3，等质因子p加1变成4时，x都已经无法被2整除了，那就更不可能被4整除了，可理解为被2榨干了\n",
    "            while p * p <= x:\n",
    "                if x % p == 0:\n",
    "                    k = 0\n",
    "                    while x % p == 0:\n",
    "                        k += 1\n",
    "                        x //= p\n",
    "                    ks[i].append(k)\n",
    "                p += 1\n",
    "            if x > 1:\n",
    "                # 若最后榨完的x还大于1，则说明最后剩余的x本身就是个质因子，该质因子的个数为1\n",
    "                ks[i].append(1)\n",
    "\n",
    "        res = 0\n",
    "        # 理想数组的结尾数字x可以为 [1, maxValue] 中的任意值\n",
    "        for x in range(1, maxValue + 1):\n",
    "            mul = 1\n",
    "            # x为1时，由于1不存在质因子，所以ks[1]为空数组。长度为n、结尾数字为1的理想数组只有1个，即 全1数组\n",
    "            for k in ks[x]:\n",
    "                mul = mul * dp[n - 1 + k][k] % mod\n",
    "            res = (res + mul) % mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "max_v = 10 ** 4 + 1\n",
    "max_k = 13\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "\n",
    "def f(x: int) -> list:\n",
    "    ks = []\n",
    "    p = 2\n",
    "    while p * p <= x:\n",
    "        if x % p == 0:\n",
    "            k = 0\n",
    "            while x % p == 0:\n",
    "                k += 1\n",
    "                x //= p\n",
    "            ks.append(k)\n",
    "        p += 1\n",
    "    if x > 1: ks.append(1)\n",
    "    return ks\n",
    "\n",
    "\n",
    "KS = [f(i) for i in range(max_v)]\n",
    "\n",
    "COR = [[0 for _ in range(max_k + 1)] for _ in range(max_k + max_v - 1)]\n",
    "COR[0][0] = COR[1][1] = COR[1][0] = 1\n",
    "for m in range(2, max_k + max_v - 1):\n",
    "    COR[m][0] = 1\n",
    "    for n in range(1, min(m, max_k) + 1):\n",
    "        COR[m][n] = (COR[m - 1][n] + COR[m - 1][n - 1]) % MOD\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(1, maxValue + 1):\n",
    "            data = 1\n",
    "            for k in KS[i]:\n",
    "                data = data * COR[n + k - 1][k] % MOD\n",
    "            res += data\n",
    "        return res % MOD\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "max_v = 10 ** 4 + 1\n",
    "max_k = 13\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "\n",
    "def f(x: int) -> list:\n",
    "    ks = []\n",
    "    p = 2\n",
    "    while p * p <= x:\n",
    "        if x % p == 0:\n",
    "            k = 0\n",
    "            while x % p == 0:\n",
    "                k += 1\n",
    "                x //= p\n",
    "            ks.append(k)\n",
    "        p += 1\n",
    "    if x > 1: ks.append(1)\n",
    "    return ks\n",
    "\n",
    "\n",
    "KS = [f(i) for i in range(max_v)]\n",
    "\n",
    "COR = [[0 for _ in range(max_k + 1)] for _ in range(max_k + max_v - 1)]\n",
    "COR[0][0] = COR[1][1] = COR[1][0] = 1\n",
    "for m in range(2, max_k + max_v - 1):\n",
    "    COR[m][0] = 1\n",
    "    for n in range(1, min(m, max_k) + 1):\n",
    "        COR[m][n] = (COR[m - 1][n] + COR[m - 1][n - 1]) % MOD\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(maxValue + 1):\n",
    "            data = 1\n",
    "            for k in KS[i]:\n",
    "                data = data * COR[n + k - 1][k] % MOD\n",
    "            res += data\n",
    "        return res % MOD - 1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\n",
    "        def fac(num):\n",
    "            h = collections.Counter()\n",
    "            if num%2 == 0:\n",
    "                h[2] += 1\n",
    "                num = num >> 1\n",
    "                while num%2==0:\n",
    "                    num = num>>1\n",
    "                    h[2] += 1\n",
    "            tmp = 3\n",
    "            while num > 1:\n",
    "                if num%tmp == 0:\n",
    "                    num = num//tmp\n",
    "                    h[tmp] += 1\n",
    "                else:\n",
    "                    tmp += 2\n",
    "            return h\n",
    "        mx = 10**9 +7\n",
    "        dp = [[0]*n for _ in range(14)] # 2^14 > 10000\n",
    "        for i in range(n):\n",
    "            dp[0][i] = 1\n",
    "        for i in range(1,14):\n",
    "            dp[i][0] = 1\n",
    "            for j in range(1,n):\n",
    "                dp[i][j] = dp[i][j-1] + dp[i-1][j]\n",
    "        idx = [{}]\n",
    "        for i in range(2,maxValue+1):\n",
    "            tmp = fac(i)\n",
    "            idx.append(tmp)\n",
    "        #print(idx)\n",
    "        res = 1\n",
    "        for i in range(2,maxValue+1):\n",
    "            count = idx[i-1]\n",
    "            tmp = 1\n",
    "            for k in count:\n",
    "                tmp *= dp[count[k]][-1]\n",
    "            res += tmp%mx\n",
    "        return res%mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Combinatorics:\n",
    "    def __init__(self, n, mod):\n",
    "        # 模板：求全排列组合数，使用时注意 n 的取值范围\n",
    "        n += 10\n",
    "        self.perm = [1] * n\n",
    "        self.rev = [1] * n\n",
    "        self.mod = mod\n",
    "        for i in range(1, n):\n",
    "            # 阶乘数 i! 取模\n",
    "            self.perm[i] = self.perm[i - 1] * i\n",
    "            self.perm[i] %= self.mod\n",
    "        self.rev[-1] = self.mod_reverse(self.perm[-1], self.mod)  # 等价于pow(self.perm[-1], -1, self.mod)\n",
    "        for i in range(n - 2, 0, -1):\n",
    "            self.rev[i] = (self.rev[i + 1] * (i + 1) % mod)  # 阶乘 i! 取逆元\n",
    "        self.fault = [0] * n\n",
    "        self.fault_perm()\n",
    "        return\n",
    "\n",
    "    def ex_gcd(self, a, b):\n",
    "        # 扩展欧几里得求乘法逆元\n",
    "        if b == 0:\n",
    "            return 1, 0, a\n",
    "        else:\n",
    "            x, y, q = self.ex_gcd(b, a % b)\n",
    "            x, y = y, (x - (a // b) * y)\n",
    "            return x, y, q\n",
    "\n",
    "    def mod_reverse(self, a, p):\n",
    "        x, y, q = self.ex_gcd(a, p)\n",
    "        if q != 1:\n",
    "            raise Exception(\"No solution.\")   # 逆元要求a与p互质\n",
    "        else:\n",
    "            return (x + p) % p  # 防止负数\n",
    "\n",
    "    def comb(self, a, b):\n",
    "        if a < b:\n",
    "            return 0\n",
    "        # 组合数根据乘法逆元求解\n",
    "        res = self.perm[a] * self.rev[b] * self.rev[a - b]\n",
    "        return res % self.mod\n",
    "\n",
    "    def factorial(self, a):\n",
    "        # 组合数根据乘法逆元求解\n",
    "        res = self.perm[a]\n",
    "        return res % self.mod\n",
    "\n",
    "    def fault_perm(self):\n",
    "        # 求错位排列组合数\n",
    "        self.fault[0] = 1\n",
    "        self.fault[2] = 1\n",
    "        for i in range(3, len(self.fault)):\n",
    "            self.fault[i] = (i - 1) * (self.fault[i - 1] + self.fault[i - 2])\n",
    "            self.fault[i] %= self.mod\n",
    "        return\n",
    "\n",
    "    def inv(self, n):\n",
    "        # 求 pow(n, -1, mod)\n",
    "        return self.perm[n - 1] * self.rev[n] % self.mod\n",
    "\n",
    "    def catalan(self, n):\n",
    "        # 求卡特兰数\n",
    "        return (self.comb(2 * n, n) - self.comb(2 * n, n - 1)) % self.mod\n",
    "class NumberTheoryPrimeFactor:\n",
    "    def __init__(self, ceil):\n",
    "        self.ceil = ceil + 100\n",
    "        self.prime_factor = [[] for _ in range(self.ceil + 1)]\n",
    "        self.min_prime = [0] * (self.ceil + 1)\n",
    "        self.get_min_prime_and_prime_factor()\n",
    "        return\n",
    "\n",
    "    def get_min_prime_and_prime_factor(self):\n",
    "        # 模板：计算 1 到 self.ceil 所有数字的最小质数因子\n",
    "        for i in range(2, self.ceil + 1):\n",
    "            if not self.min_prime[i]:\n",
    "                self.min_prime[i] = i\n",
    "                for j in range(i * i, self.ceil + 1, i):\n",
    "                    if not self.min_prime[j]:\n",
    "                        self.min_prime[j] = i\n",
    "\n",
    "        # 模板：计算 1 到 self.ceil 所有数字的质数分解（可选）\n",
    "        for num in range(2, self.ceil + 1):\n",
    "            i = num\n",
    "            while num > 1:\n",
    "                p = self.min_prime[num]\n",
    "                cnt = 0\n",
    "                while num % p == 0:\n",
    "                    num //= p\n",
    "                    cnt += 1\n",
    "                self.prime_factor[i].append([p, cnt])\n",
    "        return\n",
    "\n",
    "    def comb(self, n, m):\n",
    "        cnt = defaultdict(int)\n",
    "        for i in range(1, n + 1):  # n!\n",
    "            for num, y in self.prime_factor[i]:\n",
    "                cnt[num] += y\n",
    "        for i in range(1, m + 1):  # m!\n",
    "            for num, y in self.prime_factor[i]:\n",
    "                cnt[num] -= y\n",
    "        for i in range(1, n - m + 1):  # (n-m)!\n",
    "            for num, y in self.prime_factor[i]:\n",
    "                cnt[num] -= y\n",
    "\n",
    "        ans = 1\n",
    "        for w in cnt:\n",
    "            ans *= w ** cnt[w]\n",
    "        return ans\n",
    "\n",
    "\n",
    "mod = 10**9 + 7\n",
    "\n",
    "cb = Combinatorics(10**5, mod)\n",
    "\n",
    "nt = NumberTheoryPrimeFactor(10**5)\n",
    "\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\n",
    "        ans = 0\n",
    "        for x in range(1, maxValue+1):\n",
    "            lst = nt.prime_factor[x]\n",
    "            cur = 1\n",
    "            for _, c in lst:\n",
    "                cur *= cb.comb(c+n-1, n-1)\n",
    "                cur %= mod\n",
    "            ans += cur\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def idealArrays(self, n: int, maxValue: int) -> int:\n",
    "        mod=10**9+7\n",
    "        ret=0\n",
    "        @cache\n",
    "        def calans(x):\n",
    "            return math.factorial(n-1)//math.factorial(x-1)//math.factorial(n-x)%mod\n",
    "        @cache\n",
    "        def dfs(x,s):\n",
    "            if s>n:\n",
    "                return 0\n",
    "            if x>maxValue:\n",
    "                return 0\n",
    "            i=2\n",
    "            ret=calans(s)\n",
    "            while True:\n",
    "                if x*i>maxValue:\n",
    "                    break\n",
    "                ret+=dfs(x*i,s+1)\n",
    "                ret%=mod\n",
    "                i+=1\n",
    "            return ret%mod\n",
    "        ans=0\n",
    "        for i in range(1,maxValue+1):\n",
    "            ans+=dfs(i,1)\n",
    "            #print(i,ans)\n",
    "            ans%=mod\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
